package com.lei.binarysearch;


import java.util.Arrays;

/**
 * @Author LeiXiaoLei
 * @Date 2022/8/12 19:55
 * @Version 1.0
 */
public class BinarySearch {
    private BinarySearch() {
    }

    //非递归
    public static <E extends Comparable<E>> int search(E[] data, E target) {
        int l = 0, r = data.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) == 0) return mid;
            if (data[mid].compareTo(target) < 0) l = mid + 1;
            else r = mid - 1;
        }
        return -1;
    }

    //递归查找
    public static <E extends Comparable<E>> int searchR(E[] data, E target) {
        return searchR(data, 0, data.length - 1, target);
    }

    private static <E extends Comparable<E>> int searchR(E[] data, int l, int r, E target) {
        if (l > r) return -1;
        int mid = l + (r - l) / 2;
        if (data[mid].compareTo(target) == 0) return mid;
        if (data[mid].compareTo(target) < 0) return searchR(data, mid + 1, r, target);
        return searchR(data, l, mid - 1, target);
    }

    /**
     * 判断输入的值是否在数组中存在
     * 时间复杂度 O(logn)
     * >= target 来判断
     *
     * @param data   数组
     * @param target 目前值
     * @param <E>
     * @return true存在 false不存在
     */
    public static <E extends Comparable<E>> boolean isContain(E[] data, E target) {
        int l = 0;
        int r = data.length - 1;
        while (r > l) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) >= 0) r = mid;
            else l = mid + 1;
        }
        return data[r].compareTo(target) == 0;
    }

    /**
     * @param data   数组
     * @param target 目标值
     * @return 大于 target 的最小值索引
     */
    public static <E extends Comparable<E>> int upper(E[] data, E target) {
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) <= 0) l = mid + 1;
            else r = mid;
        }
        return l;
    }

    /**
     * @param data   数组
     * @param target 目标值
     * @return 小于 target 的最大值索引
     */
    public static <E extends Comparable<E>> int lower(E[] data, E target) {
        int l = -1, r = data.length - 1;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (data[mid].compareTo(target) >= 0) r = mid - 1;
            else l = mid;
        }
        return l;
    }


    /**
     * @param data   数组
     * @param target 目标值
     * @return 小于target 返回最大值索引 等于 target 返回最小索引
     */
    public static <E extends Comparable<E>> int lower_floor(E[] data, E target) {
        int l = lower_ceil(data, target);
        if (l + 1 < data.length && data[l + 1].compareTo(target) == 0) return l + 1;
        return l;
    }

    /**
     * @param data   数组
     * @param target 目标值
     * @return 小于等于target 返回最大值索引
     */
    public static <E extends Comparable<E>> int upper_floor(E[] data, E target) {
        int l = -1, r = data.length - 1;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (data[mid].compareTo(target) > 0) r = mid - 1;
            else l = mid;
        }
        return l;
    }


    /**
     * @param data   数组
     * @param target 目标值
     * @return 大于target 的最小值索引 等于 target 的最大索引
     */
    public static <E extends Comparable<E>> int upper_ceil(E[] data, E target) {
        int upper = upper(data, target);
        if (upper - 1 > 0 && data[upper - 1].compareTo(target) == 0) return upper - 1;
        return upper;
    }

    /**
     * @param data   数组
     * @param target 目标值
     * @return 小于target 的最大值索引 等于 target 的最小索引
     */
    public static <E extends Comparable<E>> int lower_ceil(E[] data, E target) {
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) < 0) l = mid + 1;
            else r = mid;
        }
        return r;
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 1, 3, 3, 5, 5};
        System.out.println(Arrays.toString(arr));
        for (int i = 0; i <= 6; i++) {
            boolean upper = BinarySearch.isContain(arr, i);
            System.out.println(i + " ==> "+upper);
        }
//        int[] dataSize = {1000000, 10000000};
//        for (int n : dataSize) {
//            Integer[] data = ArrayGenerator.generatorOrderedArray(n);
//            long startTime = System.nanoTime();
//            for (int i = 0; i < 100; i++) {
//                BinarySearch.search(data, n);
//            }
//            long endTime = System.nanoTime();
//            double time = (endTime - startTime) / 1000000000.0;
//            System.out.println("n = " + n + ", 100 runs: " + time + " s");
//        }
    }
}
